#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣746. 使用最小花费爬楼梯
// 【难度】简单
// 【提交】2025.10.23 https://leetcode.cn/problems/min-cost-climbing-stairs/submissions/673016658/
// 【标签】动态规划
class Solution_LC0746 {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 0;
        for(int i = 2; i <= n; ++i) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。
 * 一旦支付此费用，即可选择向上爬一个或者两个台阶。可以从下标为0或1的台阶开始爬楼梯。
 * 计算并返回达到楼梯顶部的最低花费。
 * 模型：动态规划，通过状态转移计算最小花费。
 * 
 * 二、标准解法状态设计
 * 设dp[i]表示到达第i个台阶的最小花费。
 * 状态转移方程：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
 * 初始状态：dp[0] = 0, dp[1] = 0
 * 
 * 三、你的实现思路
 * 使用动态规划方法，通过dp数组记录到达每个台阶的最小花费。
 * 对于每个台阶，选择从i-1台阶爬1步或从i-2台阶爬2步，取两者中的最小值。
 * 
 * 四、复杂度
 * 时间：O(n)，需要遍历一次数组。
 * 空间：O(n)，需要dp数组存储中间结果。
 * 
 * 五、优缺点分析
 * 优点：
 *   - 算法思路清晰，易于理解；
 *   - 时间复杂度低，能够处理较大规模数据。
 * 缺点：
 *   - 空间复杂度可以进一步优化；
 *   - 对于边界情况需要特殊处理。
 * 
 * 六、改进建议
 * 1. 可以优化空间复杂度到O(1)，只保存前两个状态；
 * 2. 可以添加输入验证：if (cost.empty()) return 0;
 * 3. 对于只有两个台阶的情况可以直接返回min(cost[0], cost[1])。
 * 
 * 七、一句话总结
 * 动态规划是解决最小花费爬楼梯问题的标准方法，你的实现准确且高效。
 */